package chapter9.作业.实践;

import chapter6.练习题.pp6_11.ListADT;
import chapter6.练习题.pp6_11.exceptions.ElementNotFoundException;
import chapter6.练习题.pp6_11.exceptions.EmptyCollectionException;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * LinkedList represents a linked implementation of a list.
 * 
 * @author Lewis and Chase
 * @version 4.0
 */
public abstract class LinkedList<T> implements ListADT<T>, Iterable<T>
{
    protected int count;
    protected LinearNode<T> head, tail;
	protected int modCount;

    /**
     * Creates an empty list.
     */
    public LinkedList()
    {
        count = 0;
        head = tail = null;
		modCount = 0;
	}
   
    /**
     * Removes the first element in this list and returns a reference
     * to it. Throws an EmptyCollectionException if the list is empty.
     *
     * @return a reference to the first element of this list
     * @throws EmptyCollectionException if the list is empty
     */
    @Override
    public T removeFirst() throws EmptyCollectionException
    {
        head=head.getNext();
        count--;
        return null;
    }
   
    /**
     * Removes the last element in this list and returns a reference
     * to it. Throws an EmptyCollectionException if the list is empty.
     *
     * @return the last element in this list
     * @throws EmptyCollectionException if the list is empty    
     */
    @Override
    public T removeLast() throws EmptyCollectionException
    {
        if (head==null){
            throw new EmptyCollectionException("LinkedList");
        }
        if (head.getNext()==null){
            head=null;
            tail=null;

        }
        else
        {
            LinearNode temp=head;
            while (head.getNext()!=null){
                if (temp.getNext()==tail){
                    tail=temp;
                    tail.setNext(null );//!!!
                    break;
                }
                temp= temp.getNext();
            }
        }
        count--;
        return null;
    }
   
    /**
     * Removes the first instance of the specified element from this
     * list and returns a reference to it. Throws an EmptyCollectionException 
     * if the list is empty. Throws a ElementNotFoundException if the 
     * specified element is not found in the list.
     *
     * @param  targetElement the element to be removed from the list
     * @return a reference to the removed element
     * @throws EmptyCollectionException if the list is empty
	 * @throws ElementNotFoundException if the target element is not found
     */
    @Override
    public T remove(T targetElement) throws EmptyCollectionException,
            ElementNotFoundException
    {
        if (isEmpty())
            throw new EmptyCollectionException("LinkedList");
      
        boolean found = false;
        LinearNode<T> previous = null;
        LinearNode<T> current = head;
      
        while (current != null && !found)
            if (targetElement.equals(current.getElement()))
                found = true;
            else
            {
                previous = current;
                current = current.getNext();
            }
            
        if (!found)
            throw new ElementNotFoundException("LinkedList");
      
        if (size() == 1)  // only one element in the list
            head = tail = null;
        else if (current.equals(head))  // target is at the head 
            head = current.getNext();
        else if (current.equals(tail))  // target is at the tail
        {
            tail = previous;
            tail.setNext(null);
        }
        else  // target is in the middle
            previous.setNext(current.getNext());
      
        count--;
		modCount++;
      
        return current.getElement();
    }
   
    /**
     * Returns the first element in this list without removing it. 
     *
     * @return the first element in this list
	 * @throws EmptyCollectionException if the list is empty
     */
    @Override
    public T first() throws EmptyCollectionException
    {
       LinearNode node =head;

        return (T) node.getElement();
    }
	
    /**
     * Returns the last element in this list without removing it. 
     *
     * @return the last element in this list  
	 * @throws EmptyCollectionException if the list is empty
     */
    @Override
    public T last() throws EmptyCollectionException
    {
        LinearNode node = head;
        while (node != null) {

            node = node.getNext();
        }
        return (T) node.getElement();
    }
	
    /**
     * Returns true if the specified element is found in this list and 
     * false otherwise. Throws an EmptyCollectionException if the list 
	 * is empty.
     *
     * @param  targetElement the element that is sought in the list
     * @return true if the element is found in this list
     * @throws EmptyCollectionException if the list is empty
     */
    @Override
    public boolean contains(T targetElement) throws
         EmptyCollectionException 
    {
        // To be completed as a Programming Project
        return false;
    }
   
    /**
     * Returns true if this list is empty and false otherwise.
     *
     * @return true if the list is empty, false otherwise
     */
    @Override
    public boolean isEmpty()
    {
        if (head.getElement()==null){
            return true;
        }
        else {
            return false;
        }
    }

    /**
     * Returns the number of elements in this list.
     *
     * @return the number of elements in the list
     */
    @Override
    public int size()
    {
        return count;
    }

    /**
     * Returns a string representation of this list.
     *
     * @return a string representation of the list    
     */
    @Override
    public String toString()
    {
        LinearNode temp=head;
        String result="";
        while (temp!=null){
            System.out.println(temp.getElement()+" ");
           // result+=temp.getElement()+" ";
            temp=temp.getNext();

        }

        return "";
    }
    public boolean find(T element){
        boolean found = false;
        LinearNode<T> previous = null;
        LinearNode<T> current = head;
        while (current!=null&&!found){
            if (element.equals(current.getElement()))
            {
                found=true;
                break;
            }
            else
            {
                current=current.getNext();
            }
        }
        return found;
    }
    public LinearNode selectionSort(LinearNode n) {
        LinearNode node = null;
        node = n;
        int min = 0;
        int temp = 0;
        LinearNode node1, node2, node3;
        node1 = node2 = node3 = n;
        while (node1.getNext() != null) {
            node3 = node2 = node1.getNext();
            min = (int) node2.getElement();
            while (node2 != null) {
                if ((int)node2.getElement() < min) {
                    node3 = node2;
                    min = (int) node2.getElement();
                }
                node2 = node2.getNext();
            }
            if (node1.getNext() != node3) {
                temp = (int) node1.getNext().getElement();
                node1.getNext().setElement(node3.getElement());
                node3.setElement(temp);
            }
            node1 = node1.getNext();
        }
        return node;
    }
    /**
     * Returns an iterator for the elements in this list. 
     *
     * @return an iterator over the elements of the list
     */
    @Override
    public Iterator<T> iterator()
    {
        return new LinkedListIterator();
    }

	/**
	 * LinkedIterator represents an iterator for a linked list of linear nodes.
	 */
	private class LinkedListIterator implements Iterator<T>
	{
		private int iteratorModCount;  // the number of elements in the collection
		private LinearNode<T> current;  // the current position
		

		public LinkedListIterator()
		{
			current = head;
			iteratorModCount = modCount;
		}
		
		/**
		 * Returns true if this iterator has at least one more element
		 * to deliver in the iteration.
		 *
		 * @return  true if this iterator has at least one more element to deliver
		 *          in the iteration
		 * @throws  ConcurrentModificationException if the collection has changed
		 *          while the iterator is in use
		 */
		@Override
        public boolean hasNext() throws ConcurrentModificationException
		{
			if (iteratorModCount != modCount) 
				throw new ConcurrentModificationException();
			
			return (current != null);
		}
		
		/**
		 * Returns the next element in the iteration. If there are no
		 * more elements in this iteration, a NoSuchElementException is
		 * thrown.
		 *
		 * @return the next element in the iteration
		 * @throws NoSuchElementException if the iterator is empty
		 */
		@Override
        public T next() throws ConcurrentModificationException
		{
			if (!hasNext())
				throw new NoSuchElementException();
			
			T result = current.getElement();
			current = current.getNext();
			return result;
		}
		
		/**
		 * The remove operation is not supported.
		 * 
		 * @throws UnsupportedOperationException if the remove operation is called
		 */
		@Override
        public void remove() throws UnsupportedOperationException
		{
			throw new UnsupportedOperationException();
		}


	}
	
}


